МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра: Автоматизовані системи управління Методичні вказівки з курсу «Компютерні мережі» Лабораторна робота №1 Тема роботи: ВИЗНАЧЕННЯ ЕНТРОПІЙНИХ ХАРАКТЕРИСТИК ОБ’ЄКТІВ КОМП’ЮТЕРНИХ МЕРЕЖ . Мета роботи: навчитися визначати ентропії джерела інформації, приймача, каналу зв’язку, системи взаємозв’язаних об’єктів. Теоретичні відомості Ентропія джерела інформації Х, що генерує незалежні повідомлення xi, обчислюється за формулою:
, (1) де p(xi)- ймовірність появи повідомлення xi; N - кількість можливих повідомлень (символів, станів об’єкту) Властивості ентропії Ентропія завжди невід’ємна:
. Ентропія максимальна, коли значення xi випадкової величини X рівноймовірні:
. (2) Максимальне значення ентропії
. (3) Для полегшення обчислень ентропії використовують наведену у додатку 1 таблицю значень добутків
Розглянемо систему, що є об’єднанням двох статистично взаємозв’язаних об’єктів, наприклад, джерела Х з можливими станами x1, xi, xn та приймача Y з можливими станами y1, yj, ym... Сумісна ентропія системи:
, (4) де
( ймовірність сумісної появи i-го стану в об’єкті X та j-го стану в об’єкті Y. Якщо об’єкти X та Y незалежні, то сумісна ентропія дорівнює сумі ентропій окремих об’єктів:
. (5) Ентропія об’єкту Y (приймача), знайдена за умови, що об’єкт Х згенерував повідомлення хi, називається частковою умовною ентропією об’єкту Y. Її визначають за формулою:
(6) де p(yj/xi) ( ймовірність події yj за умови, що в об’єкті X відбулася подія xi або ймовірність того, що приймач прийме символ yj за умови, що джерело передало символ xi. Середню або повну умовну ентропію об’єкту Y відносно об’єкту X називають просто умовною ентропією, позначають H(Y/X) і визначають за формулою:
. (7) Для незалежних об’єктів
, (8)
. (9) Формули (10) та (11) показують взаємозв’язок ентропії об’єкту, сумісної та умовної ентропій.
(10)
, (11) де H(X) ( ентропія (безумовна) об’єкту Х; H(Y) ( ентропія (безумовна) об’єкту Y; H(X,Y) – сумісна ентропія; H(Y/X) ( умовна ентропія об’єкту Y відносно об’єкту Х; H(X/Y) ( умовна ентропія об’єкту X відносно об’єкту Y. Через часткову і повну умовну ентропії описують інформаційні втрати при передачі даних в каналі зв'язку з завадами. Для цього застосовують так звані канальні матриці. В якості елементів канальної матриці звичайно використовують умовні ймовірності p(yj/xi) отримання приймачем Y символу yj за умови, що джерелом Х був відправлений символ xi. При цьому канальна матриця P(Y/X)має наступний вигляд:
. (12) Ймовірності, що є елементами головної діагоналі матриці, описують ймовірність правильного прийому. Втрати, які мали місце при передачі сигналу xi, описуються через часткову умовну ентропію:
(13) Для обчислення всіх втрат при передачі всіх сигналів використовується умовна (повна) ентропія:
(14) Для визначення ентропії приймача H(Y) за умови, що відома ентропія джерела H(X) і канальна матриця P(Y/X), необхідно знайти ймовірності появи символів на вході приймача p(yj):
. (15) Взаємозв'язок переданих і отриманих символів може бути описаний також матрицею сумісних ймовірностей P(X,Y):
. (16) Сума всіх елементів стовпчика з номером j дає p(yj), сума рядка з номером i дорівнює p(xi), а сума всіх елементів матриці рі...